package main

import (
	"fmt"
	"sort"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//dfs遍历排序查找:8ms 85%，6.2MB 15%
func kthLargest(root *TreeNode, k int) int {
	var res []int
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		res = append(res, root.Val)
		if root.Left != nil {
			dfs(root.Left)
		}
		if root.Right != nil {
			dfs(root.Right)
		}
	}
	dfs(root)
	sort.Ints(res)
	return res[len(res)-k]
}

//中序遍历倒叙:8ms 85%,6.1MB 71%
func kthLargest1(root *TreeNode, k int) int {
	var dfs func(*TreeNode)
	res := 0
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Right)
		k--
		if k == 0 {
			res = node.Val
			return
		}
		dfs(node.Left)
	}
	dfs(root)
	return res
}
func main() {
	fmt.Println(kthLargest(&TreeNode{1, nil, nil}, 1))
	fmt.Println(kthLargest1(&TreeNode{1, nil, nil}, 1))
}
